package com.itheima.leetcode.od.b.graph;

import com.itheima.datastructure.graph.Edge;
import com.itheima.datastructure.graph.Vertex;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>查找一个有向网络的头节点和尾节点</h3>
 * 给定一个有向图，图中可能包含有环，有向边用两个节点表示。第一个整数表示起始节点，第二个整数表示终止节点，如0 1表示存在从0到1的路径。每个节点用正整数表示，求这个数据的头节点与尾节点，题目给的用例会是一个头节点，但可能存在多个尾节点。同时，图中可能含有环，如果图中含有环，返回-1。
 * <p>
 * <p>
 * <p>
 * 说明：入度为0是头节点，出度为0是尾节点
 * <p>
 * 输入描述
 * <p>
 * 第一行为后续输入的键值对数量N >= 0，第二行为2N个数字。每两个为一个起点，一个终点。
 * <p>
 * 输出描述
 * <p>
 * 输出一行头节点和尾节点。如果有多个尾节点，按从大到小的顺序输出。
 * <p>
 * 备注
 * 如果图有环，输出为-1
 * <p>
 * 所有输入均合法，不会出现不配对的数据
 * <p>
 * 示例1
 * <p>
 * 输入
 * <p>
 * 4
 * <p>
 * 1 2 1 3 2 4 3 4
 * <p>
 * 1
 * <p>
 * 2
 * <p>
 * 输出
 * <p>
 * 1 4
 * <p>
 * 1
 * <p>
 * 说明
 * 该例子表示以下有向图。头节点为1，尾节点为4
 */
public class BFSFindHeadNodeAndTailNode {
    public static void main(String[] args) {
        String string = "0 1 0 2 1 2 2 3";
        System.out.println(getResult(string));
    }

    private static String getResult(String string) {
        ArrayList<String> array = Arrays.stream(string.split(" "))
                .collect(Collectors.toCollection(ArrayList::new));
        ArrayList<List<String>> list = new ArrayList<>();
        for (int i = 1; i <= array.size(); i++) {
            if (0 == (i & 1)) {
                list.add(Arrays.asList(array.get(i - 2), array.get(i - 1)));
            }
        }
        HashMap<String, Vertex> graph = new HashMap<>();
        list.stream().forEach(arr -> {
            graph.putIfAbsent(arr.get(0), new Vertex(arr.get(0)));
            graph.putIfAbsent(arr.get(1), new Vertex(arr.get(1)));
            graph.get(arr.get(0)).edges.add(new Edge(graph.get(arr.get(1))));
        });

        graph.values().stream()
                .map(vertex -> vertex.edges)
                .forEach(edges -> edges.stream().forEach(edge -> edge.linked.inDegree++));

        LinkedList<Vertex> curQueue = graph.values().stream()
                .filter(vertex -> 0 == vertex.inDegree)
                .collect(Collectors.toCollection(LinkedList<Vertex>::new));
        List<String> head = curQueue.stream()
                .map(vertex -> vertex.getName())
                .collect(Collectors.toCollection(ArrayList<String>::new));
        List<String> tails = new ArrayList<>();
        List<String> result = new ArrayList<>();

        while (!curQueue.isEmpty()) {
            LinkedList<Vertex> temQueue = new LinkedList<>();
            while (!curQueue.isEmpty()) {
                Vertex vertex = curQueue.poll();
                result.add(vertex.getName());
                // 如果fa没有后继点，即fa没有出度，则fa是尾节点
                if (1 > vertex.edges.size()) {
                    tails.add(vertex.getName());
                    continue;
                }
                for (Edge edge : vertex.edges) {
                    if (0 == --edge.linked.inDegree) {
                        temQueue.offer(edge.linked);
                    }
                }
            }
            curQueue = temQueue;
        }

        if (graph.size() != result.size()) {
            return String.valueOf(-1);
        } else {
            // 如果不存在环，则打印头节点和尾节点
            tails = tails.stream()
                    .sorted((a, b) -> b.compareTo(a))
                    .collect(Collectors.toCollection(ArrayList<String>::new));

            head.addAll(tails);

            return head.stream().collect(Collectors.joining(" "));
        }
    }
}